Efficient computation of spaced seed hashing with block indexing
Identifieur interne : 000992 ( Main/Exploration ); précédent : 000991; suivant : 000993Efficient computation of spaced seed hashing with block indexing
Auteurs : Samuele Girotto ; Matteo Comin ; Cinzia PizziSource :
- BMC Bioinformatics [ 1471-2105 ] ; 2018.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
- methods : Computational Biology.
- Algorithms, Base Sequence, Metagenomics, Time Factors.
Abstract
Spaced-seeds, i.e. patterns in which some fixed positions are allowed to be wild-cards, play a crucial role in several bioinformatics applications involving substrings counting and indexing, by often providing better sensitivity with respect to
In this work we propose a novel algorithm, Fast Indexing for Spaced seed Hashing (FISH), based on the indexing of small blocks that can be combined to obtain the hashing of spaced-seeds of any length. The method exploits the fast computation of the hashing of runs of consecutive 1 in the spaced seeds, that basically correspond to
We run several experiments, on NGS data from simulated and synthetic metagenomic experiments, to assess the time required for the computation of the hashing for each position in each read with respect to several spaced seeds. In our experiments, FISH can compute the hashing values of spaced seeds with a speedup, with respect to the traditional approach, between 1.9x to 6.03x, depending on the structure of the spaced seeds.
The online version of this article (10.1186/s12859-018-2415-8) contains supplementary material, which is available to authorized users.
Url:
DOI: 10.1186/s12859-018-2415-8
PubMed: 30497364
PubMed Central: 6266934
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000277
- to stream Pmc, to step Curation: 000277
- to stream Pmc, to step Checkpoint: 000593
- to stream PubMed, to step Corpus: 000720
- to stream PubMed, to step Curation: 000720
- to stream PubMed, to step Checkpoint: 000936
- to stream Ncbi, to step Merge: 002027
- to stream Ncbi, to step Curation: 002027
- to stream Ncbi, to step Checkpoint: 002027
- to stream Main, to step Merge: 000995
- to stream Main, to step Curation: 000992
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient computation of spaced seed hashing with block indexing</title><author><name sortKey="Girotto, Samuele" sort="Girotto, Samuele" uniqKey="Girotto S" first="Samuele" last="Girotto">Samuele Girotto</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Comin, Matteo" sort="Comin, Matteo" uniqKey="Comin M" first="Matteo" last="Comin">Matteo Comin</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Pizzi, Cinzia" sort="Pizzi, Cinzia" uniqKey="Pizzi C" first="Cinzia" last="Pizzi">Cinzia Pizzi</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">30497364</idno><idno type="pmc">6266934</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6266934</idno><idno type="RBID">PMC:6266934</idno><idno type="doi">10.1186/s12859-018-2415-8</idno><date when="2018">2018</date><idno type="wicri:Area/Pmc/Corpus">000277</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000277</idno><idno type="wicri:Area/Pmc/Curation">000277</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000277</idno><idno type="wicri:Area/Pmc/Checkpoint">000593</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000593</idno><idno type="wicri:source">PubMed</idno><idno type="RBID">pubmed:30497364</idno><idno type="wicri:Area/PubMed/Corpus">000720</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000720</idno><idno type="wicri:Area/PubMed/Curation">000720</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000720</idno><idno type="wicri:Area/PubMed/Checkpoint">000936</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000936</idno><idno type="wicri:Area/Ncbi/Merge">002027</idno><idno type="wicri:Area/Ncbi/Curation">002027</idno><idno type="wicri:Area/Ncbi/Checkpoint">002027</idno><idno type="wicri:Area/Main/Merge">000995</idno><idno type="wicri:Area/Main/Curation">000992</idno><idno type="wicri:Area/Main/Exploration">000992</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Efficient computation of spaced seed hashing with block indexing</title><author><name sortKey="Girotto, Samuele" sort="Girotto, Samuele" uniqKey="Girotto S" first="Samuele" last="Girotto">Samuele Girotto</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Comin, Matteo" sort="Comin, Matteo" uniqKey="Comin M" first="Matteo" last="Comin">Matteo Comin</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author><author><name sortKey="Pizzi, Cinzia" sort="Pizzi, Cinzia" uniqKey="Pizzi C" first="Cinzia" last="Pizzi">Cinzia Pizzi</name><affiliation><nlm:aff id="Aff1"></nlm:aff></affiliation></author></analytic><series><title level="j">BMC Bioinformatics</title><idno type="eISSN">1471-2105</idno><imprint><date when="2018">2018</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Base Sequence</term><term>Computational Biology (methods)</term><term>Metagenomics</term><term>Time Factors</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term><term>Biologie informatique ()</term><term>Facteurs temps</term><term>Métagénomique</term><term>Séquence nucléotidique</term></keywords><keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Base Sequence</term><term>Metagenomics</term><term>Time Factors</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Biologie informatique</term><term>Facteurs temps</term><term>Métagénomique</term><term>Séquence nucléotidique</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><sec><title>Background</title><p>Spaced-seeds, i.e. patterns in which some fixed positions are allowed to be wild-cards, play a crucial role in several bioinformatics applications involving substrings counting and indexing, by often providing better sensitivity with respect to <italic>k</italic>-mers based approaches. K-mers based approaches are usually fast, being based on efficient hashing and indexing that exploits the large overlap between consecutive <italic>k</italic>-mers. Spaced-seeds hashing is not as straightforward, and it is usually computed from scratch for each position in the input sequence. Recently, the FSH (Fast Spaced seed Hashing) approach was proposed to improve the time required for computation of the spaced seed hashing of DNA sequences with a speed-up of about 1.5 with respect to standard hashing computation.</p></sec><sec><title>Results</title><p>In this work we propose a novel algorithm, Fast Indexing for Spaced seed Hashing (FISH), based on the indexing of small blocks that can be combined to obtain the hashing of spaced-seeds of any length. The method exploits the fast computation of the hashing of runs of consecutive 1 in the spaced seeds, that basically correspond to <italic>k</italic>-mer of the length of the run.</p></sec><sec><title>Conclusions</title><p>We run several experiments, on NGS data from simulated and synthetic metagenomic experiments, to assess the time required for the computation of the hashing for each position in each read with respect to several spaced seeds. In our experiments, FISH can compute the hashing values of spaced seeds with a speedup, with respect to the traditional approach, between 1.9x to 6.03x, depending on the structure of the spaced seeds.</p></sec><sec><title>Electronic supplementary material</title><p>The online version of this article (10.1186/s12859-018-2415-8) contains supplementary material, which is available to authorized users.</p></sec></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Altschul, Sf" uniqKey="Altschul S">SF Altschul</name></author><author><name sortKey="Gish, W" uniqKey="Gish W">W Gish</name></author><author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name></author><author><name sortKey="Myers, Ew" uniqKey="Myers E">EW Myers</name></author><author><name sortKey="Lipman, Dj" uniqKey="Lipman D">DJ Lipman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zielezinski, A" uniqKey="Zielezinski A">A Zielezinski</name></author><author><name sortKey="Vinga, S" uniqKey="Vinga S">S Vinga</name></author><author><name sortKey="Almeida, J" uniqKey="Almeida J">J Almeida</name></author><author><name sortKey="Karlowski, Wm" uniqKey="Karlowski W">WM Karlowski</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Reinert, G" uniqKey="Reinert G">G Reinert</name></author><author><name sortKey="Chew, D" uniqKey="Chew D">D Chew</name></author><author><name sortKey="Sun, F" uniqKey="Sun F">F Sun</name></author><author><name sortKey="Waterman, M" uniqKey="Waterman M">M Waterman</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Song, K" uniqKey="Song K">K Song</name></author><author><name sortKey="Ren, J" uniqKey="Ren J">J Ren</name></author><author><name sortKey="Reinert, G" uniqKey="Reinert G">G Reinert</name></author><author><name sortKey="Deng, M" uniqKey="Deng M">M Deng</name></author><author><name sortKey="Waterman, Ms" uniqKey="Waterman M">MS Waterman</name></author><author><name sortKey="Sun, F" uniqKey="Sun F">F Sun</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author><author><name sortKey="Antonello, M" uniqKey="Antonello M">M Antonello</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author><author><name sortKey="Ornamenti, M" uniqKey="Ornamenti M">M Ornamenti</name></author><author><name sortKey="Spangaro, S" uniqKey="Spangaro S">S Spangaro</name></author><author><name sortKey="Rombo, Se" uniqKey="Rombo S">SE Rombo</name></author><author><name sortKey="Parida, L" uniqKey="Parida L">L Parida</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author><author><name sortKey="Leoni, A" uniqKey="Leoni A">A Leoni</name></author><author><name sortKey="Schimd, M" uniqKey="Schimd M">M Schimd</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Leslie, C" uniqKey="Leslie C">C Leslie</name></author><author><name sortKey="Eskin, E" uniqKey="Eskin E">E Eskin</name></author><author><name sortKey="Noble, W" uniqKey="Noble W">W Noble</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Girotto, S" uniqKey="Girotto S">S Girotto</name></author><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ounit, R" uniqKey="Ounit R">R Ounit</name></author><author><name sortKey="Wanamaker, S" uniqKey="Wanamaker S">S Wanamaker</name></author><author><name sortKey="Close, Tj" uniqKey="Close T">TJ Close</name></author><author><name sortKey="Lonardi, S" uniqKey="Lonardi S">S Lonardi</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author><author><name sortKey="Rastas, P" uniqKey="Rastas P">P Rastas</name></author><author><name sortKey="Ukkonen, E" uniqKey="Ukkonen E">E Ukkonen</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Parida, L" uniqKey="Parida L">L Parida</name></author><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author><author><name sortKey="Rombo, Se" uniqKey="Rombo S">SE Rombo</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Shajii, A" uniqKey="Shajii A">A Shajii</name></author><author><name sortKey="Yorukoglu, D" uniqKey="Yorukoglu D">D Yorukoglu</name></author><author><name sortKey="William Yu, Y" uniqKey="William Yu Y">Y William Yu</name></author><author><name sortKey="Berger, B" uniqKey="Berger B">B Berger</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Marcais, G" uniqKey="Marcais G">G Marcais</name></author><author><name sortKey="Kingsford, C" uniqKey="Kingsford C">C Kingsford</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Van Dongen, S" uniqKey="Van Dongen S">S Van Dongen</name></author><author><name sortKey="Abreu Goodger, C" uniqKey="Abreu Goodger C">C Abreu-Goodger</name></author><author><name sortKey="Enright, A" uniqKey="Enright A">A Enright</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Deorowicz, S" uniqKey="Deorowicz S">S Deorowicz</name></author><author><name sortKey="Kokot, M" uniqKey="Kokot M">M Kokot</name></author><author><name sortKey="Grabowski, S" uniqKey="Grabowski S">S Grabowski</name></author><author><name sortKey="Debudaj Grabysz, A" uniqKey="Debudaj Grabysz A">A Debudaj-Grabysz</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name></author><author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Belazzougui, D" uniqKey="Belazzougui D">D Belazzougui</name></author><author><name sortKey="Cunial, F" uniqKey="Cunial F">F Cunial</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Buhler, J" uniqKey="Buhler J">J Buhler</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name></author><author><name sortKey="Li, M" uniqKey="Li M">M Li</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name></author><author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name></author><author><name sortKey="Li, M" uniqKey="Li M">M Li</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Hahn, L" uniqKey="Hahn L">L Hahn</name></author><author><name sortKey="Leimeister, C A" uniqKey="Leimeister C">C-A Leimeister</name></author><author><name sortKey="Ounit, R" uniqKey="Ounit R">R Ounit</name></author><author><name sortKey="Lonardi, S" uniqKey="Lonardi S">S Lonardi</name></author><author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name></author><author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name></author><author><name sortKey="Mansouri Bigvand, A" uniqKey="Mansouri Bigvand A">A Mansouri Bigvand</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Noe, L" uniqKey="Noe L">L Noé</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Leimeister, C A" uniqKey="Leimeister C">C-A Leimeister</name></author><author><name sortKey="Boden, M" uniqKey="Boden M">M Boden</name></author><author><name sortKey="Horwege, S" uniqKey="Horwege S">S Horwege</name></author><author><name sortKey="Lindner, S" uniqKey="Lindner S">S Lindner</name></author><author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Onodera, T" uniqKey="Onodera T">T Onodera</name></author><author><name sortKey="Shibuya, T" uniqKey="Shibuya T">T Shibuya</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Rumble, Sm" uniqKey="Rumble S">SM Rumble</name></author><author><name sortKey="Lacroute, P" uniqKey="Lacroute P">P Lacroute</name></author><author><name sortKey="Dalca, Av" uniqKey="Dalca A">AV Dalca</name></author><author><name sortKey="Fiume, M" uniqKey="Fiume M">M Fiume</name></author><author><name sortKey="Sidow, A" uniqKey="Sidow A">A Sidow</name></author><author><name sortKey="Brudno, M" uniqKey="Brudno M">M Brudno</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bucher, P" uniqKey="Bucher P">P Bücher</name></author><author><name sortKey="Moret, Bme" uniqKey="Moret B">BME Moret</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="B Inda, K" uniqKey="B Inda K">K Břinda</name></author><author><name sortKey="Sykulski, M" uniqKey="Sykulski M">M Sykulski</name></author><author><name sortKey="Kucherov, G" uniqKey="Kucherov G">G Kucherov</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Girotto, S" uniqKey="Girotto S">S Girotto</name></author><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ounit, R" uniqKey="Ounit R">R Ounit</name></author><author><name sortKey="Lonardi, S" uniqKey="Lonardi S">S Lonardi</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Brown, Dg" uniqKey="Brown D">DG Brown</name></author><author><name sortKey="Li, M" uniqKey="Li M">M Li</name></author><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mohamadi, H" uniqKey="Mohamadi H">H Mohamadi</name></author><author><name sortKey="Chu, J" uniqKey="Chu J">J Chu</name></author><author><name sortKey="Vandervalk, Bp" uniqKey="Vandervalk B">BP Vandervalk</name></author><author><name sortKey="Birol, I" uniqKey="Birol I">I Birol</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Girotto, S" uniqKey="Girotto S">S Girotto</name></author><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Girotto, S" uniqKey="Girotto S">S Girotto</name></author><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Keich, U" uniqKey="Keich U">U Keich</name></author><author><name sortKey="Li, M" uniqKey="Li M">M Li</name></author><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name></author><author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Girotto, S" uniqKey="Girotto S">S Girotto</name></author><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name></author><author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wood, De" uniqKey="Wood D">DE Wood</name></author><author><name sortKey="Salzberg, Sl" uniqKey="Salzberg S">SL Salzberg</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Leimeister, C A" uniqKey="Leimeister C">C-A Leimeister</name></author><author><name sortKey="Sohrabi Jahromi, S" uniqKey="Sohrabi Jahromi S">S Sohrabi-Jahromi</name></author><author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name></author></analytic></biblStruct></listBibl></div1></back></TEI><affiliations><list></list><tree><noCountry><name sortKey="Comin, Matteo" sort="Comin, Matteo" uniqKey="Comin M" first="Matteo" last="Comin">Matteo Comin</name><name sortKey="Girotto, Samuele" sort="Girotto, Samuele" uniqKey="Girotto S" first="Samuele" last="Girotto">Samuele Girotto</name><name sortKey="Pizzi, Cinzia" sort="Pizzi, Cinzia" uniqKey="Pizzi C" first="Cinzia" last="Pizzi">Cinzia Pizzi</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000992 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000992 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= PMC:6266934
|texte= Efficient computation of spaced seed hashing with block indexing
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:30497364" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |